package 剑指offer.变态跳台阶_9;
/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * @author x
 * @summary
 */
public class Main {
    public int JumpFloorII(int target) {
    	if(target == 1)	return 1;
        if(target == 2)	return 2;
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < target; i++){
        	for(int j = 0; j < i; j++){
        		dp[i] += dp[j];
        	}
            dp[i] += 1;
        }
        return dp[target-1];
    }
    
    /**
f(n)=f(n-1)+f(n-2)+...+f(1) + 1(一下跳到n）
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)+1
所以f(n)=2*f(n-1)
     */
    public int JumpFloorII2(int target) {
    	if(target == 1)	return 1;
        if(target == 2)	return 2;
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < target; i++){
        	dp[i] = 2*dp[i-1];
        }
        return dp[target-1];
    }
    
    /**
     * 设跳上n级总共有f（n）种跳法，n-1级总共有f（n-1）,n-2级总共有f（n-2）种跳法种跳法。。。则：
f(n) = 1+f(n-1)+f(n-2)+...+f(2)+f(1);//1代表的意思是n级台阶跳n级的跳法只有一种
f(1) = 1;
所以：
f(2)=1+f(1)=1+1=2=2^1;
f(3)=1+f(2)+f(1)=1+2+1=4=2^2;
f(4)=1+f(3)+f(2)+f(1)=1+4+2+1=8=2^3;
......
归纳：
f(n) = 2^(n-1);（n>=1的整数）
     */
    public int JumpFloorII3(int target) {
        return (int)Math.pow(2,target-1);
   }
}
